#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * @brief The Solution class 分割回文串2
 */
class Solution {
public:
    Solution(): n(0)
    {

    }
public:
    int minCut(const string& s) {
        n = s.size();
        if(n == 1) return 0;

        // 所有范围判断是否为回文数记录起来 0=未确认 1=是 -1=不是
        vector<vector<bool>> g(n,vector<bool>(n, true));
        for(int i = n-1; i>=0; i--)
        {
            for(int j = i + 1; j < n; j++)
            {
                g[i][j] = s[i] == s[j] && g[i+1][j-1];
            }
        }

        vector<int> f(n, INT_MAX);
        for(int i = 0; i < n; i++)
        {
            if(g[0][i])
            {
                f[i] = 0;
            }else
            {
                for(int j = 0; j<i; j++)
                {
                    if(g[j+1][i])
                    {
                        // 找出i范围内，最后一个回文串
                        f[i] = std::min(f[i],f[j]+1);
                    }
                }
            }
        }


        return f[n-1];
    }


private:
    int n;
};

//int main()
//{
//    Solution solution;
//    // s = "aab" 分割1次 aa/b
////    string s = "aab";
////    string s = "a";
////    string s = "ab";
//    string s = "abbab";
//    int ret = solution.minCut(s);
//    cout << "ret: " << ret << endl;
//}
